Generator matrix

 ( Coding Theory ) 

In coding theory, a generator matrix is a matrix whose rows form a basis for a linear code. The codewords are all of the linear combinations of the rows of this matrix, that is, the linear code is the row space of its generator matrix.

---

Terminology If G is a matrix, it generates the codewords of a linear code C by

$w=sG$

where w is a codeword of the linear code C, and s is any input vector. Both w and s are assumed to be row vectors.

A generator matrix for a linear $n,\_q$-code has format $k\; \backslash times\; n$, where n is the length of a codeword, k is the number of information bits (the dimension of C as a vector subspace), d is the minimum distance of the code, and q is size of the finite field, that is, the number of symbols in the alphabet (thus, q = 2 indicates a binary code, etc.). The number of redundant bits is denoted by $r\; =\; n\; -\; k$.

The standard form for a generator matrix is,

$G\; =\; \backslash begin\{bmatrix\}\; I\_k\; |\; P\; \backslash end\{bmatrix\}$,

where $I\_k$ is the $k\; \backslash times\; k$ identity matrix and P is a $k\; \backslash times\; (n-k)$ matrix. When the generator matrix is in standard form, the code C is Systematic code in its first k coordinate positions.

A generator matrix can be used to construct the parity check matrix for a code (and vice versa). If the generator matrix G is in standard form, $G\; =\; \backslash begin\{bmatrix\}\; I\_k\; |\; P\; \backslash end\{bmatrix\}$, then the parity check matrix for C is

$H\; =\; \backslash begin\{bmatrix\}\; -P^\{\backslash top\}\; |\; I\_\{n-k\}\; \backslash end\{bmatrix\}$,

where $P^\{\backslash top\}$ is the transpose of the matrix $P$. This is a consequence of the fact that a parity check matrix of $C$ is a generator matrix of the dual code $C^\{\backslash perp\}$.

G is a $k\; \backslash times\; n$ matrix, while H is a $(n-k)\; \backslash times\; n$ matrix.

---

Equivalent codes Codes C₁ and C₂ are equivalent (denoted C₁ ~ C₂) if one code can be obtained from the other via the following two transformations:

1. arbitrarily permute the components, and
2. independently scale by a non-zero element any components.

Equivalent codes have the same minimum distance.

The generator matrices of equivalent codes can be obtained from one another via the following elementary operations:

1. permute rows
2. scale rows by a nonzero scalar
3. add rows to other rows
4. permute columns, and
5. scale columns by a nonzero scalar.

Thus, we can perform Gaussian elimination on G. Indeed, this allows us to assume that the generator matrix is in the standard form. More precisely, for any matrix G we can find an invertible matrix U such that $UG\; =\; \backslash begin\{bmatrix\}\; I\_k\; |\; P\; \backslash end\{bmatrix\}$, where G and $\backslash begin\{bmatrix\}\; I\_k\; |\; P\; \backslash end\{bmatrix\}$ generate equivalent codes.

---

See also

• Hamming code (7,4)

---

Notes

---

Further reading

---

External links

• Generator Matrix at MathWorld

Post Comment